#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=200 lang=cpp
 *
 * [200] 岛屿数量
 */

// @lc code=start
int dxdy[][4] = {
    {0, 0, 1, -1},
    {1, -1, 0, 0}
};
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int res = 0;
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    res++; dfs(i, j, grid);
                }
            }
        }
        return res;
    }

    void dfs(int x, int y, vector<vector<char>> & grid) {
        grid[x][y] = '0';
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < 4; i++) {
            int dx = x + dxdy[0][i], dy = y + dxdy[1][i];
            if (dx >= 0 && dx < m && dy >= 0 && dy < n && grid[dx][dy] == '1')
                dfs(dx, dy, grid);
        }
    }
};
// @lc code=end

